package com.njupt.Tree;

import com.njupt.Tree.TreeNode;


import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/28 15:04
 * @Description: 257. 二叉树的所有路径
 * @Version: 1.0
 */


public class BinaryTreePaths {

    /**
     * 二叉树后续遍历非递归算法
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> results = new ArrayList<>();
        Deque<TreeNode> treeStack = new LinkedList<>();
        Deque<Boolean> stack = new LinkedList<>();
        TreeNode cur = root;
        Boolean flag = false;
        while(cur != null || !treeStack.isEmpty()){
            if(cur != null){
                treeStack.push(cur);
                stack.push(false);
                cur = cur.left;
            }else {
                cur = treeStack.pop();
                flag = stack.pop();
                if(flag == false){
                    treeStack.push(cur);
                    stack.push(true);
                    cur = cur.right;
                }else {
                    //访问节点
                    if(cur.left == null && cur.right == null){
                        Iterator<TreeNode> iterator = treeStack.iterator();
                        StringBuilder sb = new StringBuilder();
                        sb.insert(0,cur.val);
                        sb.insert(0,"->");
                        while(iterator.hasNext()){
                            sb.insert(0,iterator.next().val);
                            sb.insert(0,"->");
                        }
                        sb.delete(0,2);
                        results.add(sb.toString());
                    }
                    cur = null;
                }
            }
        }
        return results;
    }

    /**
     * 先序遍历递归算法
     * @param root
     * @return
     */
    public List<String> binaryTreePaths1(TreeNode root) {
        List<String> results = new ArrayList<>();
        String path="";
        if(root == null) return  results;
        traverse1(root,path,results);

        return results;

    }

    private void traverse(TreeNode root, List<Integer> path, List<String> results) {
        path.add(root.val);
        //递归的终止条件，叶子节点，记录path路径到results中，并返回
        if(root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size()-1; i++) {
                String s = String.valueOf(path.get(i));
                sb.append(s+ "->");
            }
            sb.append(path.get(path.size()-1));
            results.add(sb.toString());
            return;
        }

        if(root.left != null){
            traverse(root.left,path,results);  //递归
            path.remove(path.size()-1); //回溯
        }
        if(root.right != null){
            traverse(root.right,path,results);  //递归
            path.remove(path.size()-1);   //回溯
         }
    }


    private void traverse1(TreeNode root, String path, List<String> results) {
        path += root.val;
        //递归的终止条件，叶子节点，记录path路径到results中，并返回
        if(root.left == null && root.right == null){
            results.add(path);
            return;
        }

        if(root.left != null){
            traverse1(root.left,path + "->",results);  //递归

        }
        if(root.right != null){
            traverse1(root.right,path + "->",results);  //递归

        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);


        BinaryTreePaths test = new BinaryTreePaths();
        List<String> list = test.binaryTreePaths1(root);
        System.out.println(list);
//        for (String str:list){
//            System.out.println(str);
//        }


    }
}
